在复仇後，尊者并未得到复仇的快感，反而开始生起悔疚罪业的心。在这种日益折磨他内心的罪疚感变得越来越强时，尊者便辗转来到了着名的玛尔巴译师居地。玛尔巴是一位居士，曾不畏危险多次远赴印度，依止那诺巴等大师修学，更带回大量珍贵佛典，成为了在藏地受人敬重的大译师及大修行者。透过玛尔巴的神通，他知道了密勒日巴的杀人重罪，同时也知道尊者有缘成为他的上首弟子。玛尔巴早已是一位证悟了无上慈悲心的大成就者，但为了令密勒日巴忏净罪障，他便对尊者拳打脚踢，又命尊者为他在山上建造大型楼房，自己却表现为脾气暴躁、不近人情及常常饮酒的人。尊者为了替师父建房，身心被折磨得很利害。玛尔巴更规定尊者要以背扛大石上山，令尊者背部被磨至溃烂不堪。在每次建成一楼房後，玛尔巴却会发脾气命尊者把房子拆去重建为不同形状。就这样，尊者不屈不挠地捱着痛苦折磨及责打多年。在这期间，玛尔巴常有对其他弟子开示，却从不允许尊者参与闻法，更多次施以责打。这样地过了多年後，玛尔巴才对尊者说：「你是我有缘的弟子。这些年来，为了令你洗尽极重的罪业，我才对你多番留难。这些磨难你本应历受九 次，但因着你师母的阻挠，我只施行了八次！」。自此，译师便终於对尊者开示，并授记尊者将成为极为杰出的行者。

  尊者修行时，是在山洞中进行的。在上座时，尊者会头顶一油灯，至油枯灯灭方肯下座略事休息。有一次，尊者梦见家宅已全毁，母亲老逝，其妹如乞丐般流浪，於是向玛尔巴辞行。玛尔巴对他说：「世事本就是无常，你去了也没有甚麽意思，但你要去便去吧！今後我俩恐怕再见不上面了！」，便对他授予了最深妙的耳传心诀。这些心诀，玛尔巴只给予密勒日巴，并未授予其他弟子，更嘱咐密勒日巴只能传予最有根器的一位弟子，又叫尊者在看透世间无常後，便应往冈底斯山及喜玛拉雅山圣母峰等的山洞中努力修行。

  尊者回乡後，发现家乡已人面全非，其家族大楼已成败瓦，母亲早已死去，妹妹不知所踪。在已变为废墟的大宅中，尊者体悟了无常，顿时入於定中竟达七日。在出定後，尊者走上了终生在洞中修行的生涯。

  在跟着下来的日子中，尊者便流浪於一个山洞及另一个山洞间，隐迹人间。尊者从不下山乞食，在没有粮食时便取山间荨麻而吃。这种苦行导致他身泛绿色，头发也变成呈绿色的怪异情况 。在冰天雪地中，尊者只穿单层的棉布，有时更因布料最终烂了而赤身露体。此时，尊者心中只念及修行及自己的罪业深重，对世俗的眼光及饭食等事已不挂在心上。由於他的内火修持有成，在他周围的冰雪都会融化，这便吸引了山下人民的注意。为了避开来朝礼的人，尊者便遁入更深的山中。在这样地在无人山洞中苦行多年後，尊者最终证得了即身成佛的境界，并以佛法摄受了很多弟子，其中包括了本欲来挑战的魔类。

  尊者在世寿八十四岁时示寂，终其一生，绝大部份的时光都是在不同的山洞中修持渡过的。在後期，尊者已证得神通，迁洞时便以神通飞行至另一个洞，其一生中住过的洞有很多，现在这些地方都被视为圣地及修持闭关的最佳地点。

  密勒日巴的形相，在後世多绘为身泛绿色、披白色棉布的长发体瘦苦行相。

  在尊者的一生中，分别对弟子及在深山中遇上的猎人等以唱歌的方式开示极多。这些歌的内容，有些是其修行的过程，有些是对修行人的导引，也有些是他自己的证境之描述。这些道歌，在後世被结集为《十万道歌》，是藏族学者研究的对像、修行人的导引及民间的歌谣。尊者的开示传承， 主要付托予冈布巴大师，成为了现今称为「噶举派」的教法。

  除了其道歌及传承外，尊者当年为师所建的九层大楼，至今仍可在西藏见到。